In design of communications systems, there is generally a compromise between bit error rate (BER) and transmission bit rate. Higher bit rates tend to have higher BERs. A well-known limit on capacity of a communications channel is the Shannon Limit. In practice, where forward error correction (FEC) is used, the Shannon Limit is a theoretical boundary on channel capacity for a given modulation and code rate, where the code rate is the ratio of data bits to total bits transmitted per unit time. FEC coding adds redundancy to a message by encoding such a message prior to transmission. Some example error correction codes include Hamming, Bose-Chaudhuri-Hochquenghem (BCH), Reed-Solomon (RS), Viterbi, trellis, etc.
Several of these codes have been standardized in the International Telecommunication Union Telecommunication Standardization Sector (ITU-T) G.975 and G.709. For example, the standardized Reed-Solomon (255, 239) code has a net coding gain (NCG) of 6.2 dB at a 10-15 decoder output bit error rate (BER) with a 6.69% redundancy ratio. However, for high-speed (10 Gb/s and beyond) communication systems, more powerful forward error correction (FEC) codes have become necessary in order to achieve greater correction capability to compensate for serious transmission quality degradation.
More recently, Super-FEC coding schemes have been developed that utilize a combination of two or more encoding schemes to provide greater BER correction capability and increase throughput. Generally, RS encoding is combined with another encoding. For example, ITU-T G.975.1 I.4 specifies a concatenation of RS and BCH encoding schemes. Due to its high performance, RS encoding is expected to remain in widespread use for FEC encoding and a variety of Super-FEC coding schemes.
Reed-Solomon codes are systematic block codes used for error correction. Input data is partitioned into data blocks containing K symbols. Each block of K input symbols is used to generate R check/parity symbols. The combination of K input symbols and R check/parity symbols are concatenated to form an L symbol codeword that may be used to detect and correct corruption of the codeword.
The R check/parity symbols correspond to the remainder polynomial from finite field polynomial division, where the dividend polynomial is given by the block of K input symbols and the divisor polynomial is a code generator polynomial, G(t), given by the particular Reed-Solomon code that is being used. The code generator polynomial of order R, takes the form:G(y)=yR+CR-1*yR-1+C2*y2+C1*y+C0,Cr=1.The generator polynomial is an irreducible polynomial having a number of coefficients (M), which is equal to the number of check/parity symbols in each code block.
Evaluating the remainder polynomial from finite field polynomial division is a complex operation requiring significant resources such as circuit area and computation time. In an application that continuously generates Reed-Solomon-encoded data, the evaluation of the remainder polynomial needs to achieve a throughput rate that equals or exceeds the data rate of the vectors of input symbols.
A standard Reed-Solomon encoder evaluates the remainder polynomial in a recursive process requiring K iterations. Each iteration requires multiple, simultaneous, finite field multiplications and additions/subtractions. To calculate the modulus of the division, an incomplete remainder is maintained throughout the calculation. In each iteration t (0<t<=K), the remainder X(t) is calculated by subtracting a new data symbol, D(t), from the most significant symbol (XR-1) of the previously calculated remainder X(t−1), and the result is multiplied by the generator polynomial G(y) and subtracted from X(t−1):X(t)=X(t−1)−G(y)*(Sig(XR-1(t−1)−D(t))
For high-speed communication applications, parallel processing may be needed to meet throughput requirements. One approach to parallelize Reed-Solomon encoding implements multiple instances of the standard encoder, and each instance decodes a separate data block or data channel. Another approach modifies the standard Reed-Solomon encoder to process multiple data blocks of multiple data channels in a time-division-multiplexed (TDM) fashion. Neither of these approaches is desirable because the former solution increases hardware requirements linearly as the number of channels increases, and the latter solution increases latency of the encoding.
One or more embodiments may address one or more of the above issues.